Global-based communications networks such as the Internet have evolved from an early, research-based system with limited access, to a truly world wide network with millions of users. The original network protocol, TCP/IP, was designed on the basis that system users would connect to the network for strictly legitimate purposes. As a consequence, no particular consideration was given to security issues. In recent years, however, the incidence of malicious attacks on the Internet has grown to an alarming proportion. These attacks, which take on a variety of forms, often lead to a complete disruption of service for a targeted victim.
One such attack is based on the concept of flooding a victim with so much traffic that the victim's server cannot cope, or with very effective malicious packets at lower rates. Due to its anonymous nature, the Internet Protocol (IP) makes it extremely difficult to precisely identify the real source of any given datagram, and thus any given flow, if the source wishes to remain unknown. This peculiarity is often exploited, during a malicious Denial of Service (DoS) attack, to hide the source of the attack. A DoS attack involves blocking somebody's ability to use a given service on the network. DoS attacks are common across the Internet with many being launched daily at various targets.
Thus, if an attacker uses a spoofed source address—i.e. replaces its legitimate address with an different/illegitimate one—it is very difficult to trace the real source of the attack. It is expected that if attackers were open to identification the incidence of DoS attacks would decrease significantly.
Several methods have been proposed for solving the IP trace back problem. A thorough overview on the topic is given by H. F. Lipson in a special report entitled “Tracking and Tracing Cyber-Attacks: Technical Challenges and Global Policy Issues”, CERT Coordination Center. Among all the other techniques that this paper describes, a hop-by-hop trace back scheme is discussed. This mechanism consists of a manual and tedious process by which an administrator gathers information on each router on the upstream path of the flow being traced one step at a time until the source is reached.
Other prior art solutions involve systems where routers are requested to insert their IP addresses, or other unique identifiers, into IP packet headers with a certain probability. This method relies on the victim of an attack reconstructing the path by using the information gathered by correlating all the received, marked datagrams. This system is described by S. Savage, D. Wetherall, A. Karling and T. Anderson in “Practical Network Support for IP Trace back”, SIGOMM'00, Stockholm, Sweden.
The iTrace method relies on routers sending a new type of Internet control message protocol (ICMP) message to the destination of the datagram examined with a certain probability. By gathering a given number of these messages the receiver of a certain flow can reconstruct the path to the source. This method is described by S. Bellovin, M. Leech, T. Taylor, “ICMP Trace back messages”, IETF work in progress.
In a hash-based solution every router keeps a table containing a hashed value from every packet forwarded during a given interval. If a particular flow is to be traced, routers on the upstream path forward their tables to an entity that will carry out a correlation process to determine the next hop. The method relies on Bloom filters to speed up the look-up process in the table. This method is described by C. Snoeren, C. Patridge, L. Sanchez et al., “Hash-based IP Trace back”, SIGCOMM'01, San Diego.
End-to-end IP trace back across multiple Autonomous Systems (AS) is still an unsolved problem although some work is being done by the IETF in an attempt to define a common framework to achieve this goal.
The present invention focuses on one of the many issues IP trace back frameworks are faced with: how to trace a flow from one end to another of a single AS given the signature and the egress point of the flow.
All the other methods described above could potentially be employed to solve the same problem, but they all generally carry too much overhead. Since all these methods were primarily designed to work across multiple Autonomous Systems, they are computationally intensive and/or require an extensive usage of network resources if compared to the proposed solution. For example: both the hash-based and iTrace methods need Public Key Infrastructures; or all methods need to have the “marking mechanisms” always turned on; or all methods are demanding in terms of memory: either for storing a hashed value of every forwarded packet or for storing marking values from millions of packets as it will be exemplified later.
Finally all the mentioned prior art methods have trouble—or are not effective at all—in the case of Distributed Denial of Service (DDoS) attacks. In a DDoS attack several sources are involved directly or indirectly to carry out an attack on a victim. The only realistic solution is the Hop-by-Hop IP trace back method which is not a clearly defined technique but rather a lengthy procedure based on the available equipment and the experience of the administrator.
There is, therefore, a need for methods and systems for identifying a source of a packet flow in a communication system.